package dichotomy.find.min.number.in.rotate.array;
/**
 * @Time 2020/1/14
 * @author 王光浩
 * @Need 给出一个升序的整型数组，该数组在某处进行了旋转，旋转方式如下（123456->4561234），请找出旋转
 *       后的数组中最小元素值。需要注意点：首先数组中不存在重复元素，然后旋转点可能在数组的第一个元素处
 *       这样就相当于没有进行旋转。
 * @Thinking 使用通用的二分法。
 *           使用二分法进行求解，循环结束的条件是later>previous，循环体内部的逻辑为如果later所在
 *           下标值大于mid下标所在的元素，则将later=mid-1，否则将previous=mid+1。
 *           复杂度分析：时间复杂度O（logn），空间复杂度O（1）
 */
public class OthersMethod {
    public int findMin(int[] nums) {
    	int later=nums.length;
    	int previous=0;
    	int mid;
    	if(nums[later]>=nums[previous])return nums[previous];
    	while(later>=previous) {
    		mid=previous+(later-previous)/2;
    		//判断mid下标附近是否存在最小值
    		if(nums[mid]>nums[mid+1])
    			return nums[mid+1];
    		if(nums[mid-1]>nums[mid])
    			return nums[mid];
    		//更改左右下标值
    		if(nums[previous]>nums[mid])
    			previous=mid+1;
    		else
    			later=mid-1;
    	}
    	return previous;
    }
	
}
